package com.example.javamaday.leetcode;

public class LeetCodeTest0338 {

    public static void main(String[] args) {
        new LeetCodeTest0338().countBits(12);
    }

    public int[] countBits(int n) {
        int[] result = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            result[i] = countOne(i);
        }
        return result;
    }

    private int countOne(int n) {
        if (n < 2) {
            return n;
        }
        StringBuilder builder = new StringBuilder();
        int common = 2;
        while (common * 2 <= n) {
            common *= 2;
        }
        while (n >= 0 && common >= 1) {
            if (n >= common) {
                builder.append(1);
                n -= common;
                common /= 2;
            } else {
                builder.append(0);
                common /= 2;
            }
        }
        return builder.toString().replaceAll("0", "").length();
    }
}
